Fitness Clouds and Problem Hardness in Genetic Programming

Leonardo Vanneschi², Manuel Clergue¹, Philippe Collard¹, Marco Tomassini², and Sébastien Vérel¹

¹I3S Laboratory, University of Nice, Sophia Antipolis, France

²Information Systems Department, University of Lausanne, Lausanne, Switzerland

Abstract. This paper presents an investigation of genetic programming fitness landscapes. We propose a new indicator of problem hardness for tree-based genetic programming, called negative slope coefficient, based on the concept of fitness cloud. The negative slope coefficient is a predictive measure, i.e. it can be calculated without prior knowledge of the global optima. The fitness cloud is generated via a sampling of individuals obtained with the Metropolis-Hastings method. The reliability of the negative slope coefficient is tested on a set of well known and representative genetic programming benchmarks, comprising the binomial-3 problem, the even parity problem and the artificial ant on the Santa Fe trail.

LNCS 3103, p. 690 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004